package DataStructure;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

//LRU缓存
public class LRU<K extends Comparable<K>,V> {
    private final int size;
    private final Map<K,V> cache;
    private final List<K> queryList;

    public LRU(int size) {
        this.size = size;
        this.cache=new HashMap<>();
        this.queryList=new LinkedList<>();
    }

    public V get(K key) {
        if (!cache.containsKey(key)) {
            return null;
        }
        V value = cache.get(key);
        queryList.remove(key);
        queryList.add(key);
        return value;
    }

    public void put(K key, V value) {
        if (cache.containsKey(key)) {
            queryList.remove(key);
        } else {
            //移除最旧的
            if (cache.size() >= size) {
                K old = queryList.remove(0);
                cache.remove(old);
            }
        }
        //添加或更新
        cache.put(key,value);
        queryList.add(key);

    }

    @Override
    public String toString() {
        return "LRU{" +
                "queryList=" + queryList +
                '}';
    }
}
